package com.wcj.test;

/**
 * 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，
 * 即把一个数组最开始的若干个元素搬到数组的末尾，
 * 变成一个旋转数组，比如变成了[3,4,5,1,2]，
 * 或者[4,5,1,2,3]这样的。
 * 请问，给定这样一个旋转数组，求数组中的最小值。
 */
public class 旋转数组中的最小数字 {

    /**
     * 只能处理无重复
     * @param array
     * @return
     */
    public int minNumberInRotateArray2(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while (left != right){
            if (array[left] > array[right]){
                left++;
                right--;
            }else if (array[left] <= array[right]){
                left++;
            }
        }
        return array[--right];
    }

    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right){
            int mid = (left + right) / 2;
            if (array[mid] > array[right]){
                left = mid + 1;
            }else if (array[mid] == array[right]){
                right--;
            }else {
                right = mid;
            }
        }
        return array[left];
    }
}
